package com.xufx.algorithm.dynamicplan;

/**
 * leetcode 55. Jump Game
 * @link https://leetcode.cn/problems/3sum/description/
 * You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
 *
 * Return true if you can reach the last index, or false otherwise.
 *
 * example:
 * Input: nums = [2,3,1,1,4]
 * Output: true
 * Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
 *
 * Notice that the order of the output and the order of the triplets does not matter.
 *
 * NOTICE: 经典动态规划，要一步步找出规律，其实不按照动态规划的思想也能做。不难
 */
public class Leetcode55JumpGame {

    public static void main(String[] args) {
        int[] nums = new int[]{2, 3, 1, 1, 4};
        boolean result = canJump(nums);
        System.out.println("bingo==" + result);
    }

    private static boolean canJump(int[] nums){
        int len = nums.length;
        if(len == 1){
            return true;
        }
        boolean[] f = new boolean[len];
        f[0] = true;
        for(int i = 1; i < len; i++){
            for (int j = 0; j < i; j++){
                if(f[j] && nums[j] >= i - j){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[len - 1];
    }
}
